package structures.stack;


import java.util.Stack;

// 逆波兰表达式 --> 中缀表达式转后缀表达式
public class PolandNotation2 {
    public static void main(String[] args) {
        String expression = "1+((2+3)X4)-5";
        Stack<Character> characterStack = new Stack<>();
        Stack<Character> tempStack = new Stack<>();

        for (int index = 0; index < expression.length(); index++) {
            char charAt = expression.charAt(index);

            // 遇到操作数 直接入栈 characterStack
            if (isOperOrNum(charAt) == 3) {
                characterStack.push(charAt);
                continue;
            }

            // 为 操作符
            while (isOperOrNum(charAt) > 0) {
                // tempStack为空 或者 tempStack栈顶为( 则直接入栈
                if (tempStack.isEmpty() || tempStack.peek() == '(') {
                    tempStack.push(charAt);
                    break;
                }

                // 如果优先级比tempStack栈顶运算符高 则直接入 tempStack
                if (isOperOrNum(charAt) > isOperOrNum(tempStack.peek())) {
                    tempStack.push(charAt);
                    break;
                }

                // 优先级比栈顶的低  则把栈顶运算符压入 characterStack 再次比较优先级
                Character popChar = tempStack.pop();
                characterStack.push(popChar);
            }

            // 为 符号 ( )
            if (isOperOrNum(charAt) < 0) {
                // ( 直接入 tempStack
                if (charAt == '(') {
                    tempStack.push(charAt);
                    continue;
                }
                // ) 一次弹出 tempStack de 运算符入 characterStack 直到遇到 ( 此时将 () 丢弃
                if (charAt == ')') {
                    while (tempStack.peek() != '(') {
                        characterStack.push(tempStack.pop());
                    }
                    // 去除 (  )w为charAt不处理则自动去除
                    tempStack.pop();
                }
            }
        }
        // 将tempStack剩余的操作符直接入栈
        while (!tempStack.isEmpty()) {
            characterStack.push(tempStack.pop());
        }

        // 遍历 characterStack 获取所有数据 然后翻转获取逆波兰表达式
        StringBuilder stringBuilder = new StringBuilder();
        while (!characterStack.isEmpty()) {
            stringBuilder.append(String.valueOf(characterStack.pop())).append(" ");
        }
        stringBuilder.deleteCharAt(stringBuilder.length() - 1);
        StringBuilder reverseStringBuilder = stringBuilder.reverse();
        System.out.println("---转换结果: " + reverseStringBuilder.toString() + " ----");

    }

    private static int isOperOrNum(char ch) {
        int ret = 0;
        switch (ch) {
            case '+':
            case '-':
                ret = 1;
                break;
            case '*':
            case '/':
            case 'x':
            case 'X':
                ret = 2;
                break;
            case '0':
            case '1':
            case '2':
            case '3':
            case '4':
            case '5':
            case '6':
            case '7':
            case '8':
            case '9':
                ret = 3;
                break;
            case '(':
            case ')':
                ret = -1;
                break;
        }
        return ret;
    }

}
